A packet switching network has switching points or nodes for transmissions of data among senders and receivers connected to the network. The switching performed by these switching points is in fact the action of passing on packets of data received by a switching point or node to a further node in the network. Such switching actions are the means by which communication data is moved through the packet switching network.
Each node may comprise a packet processor configured to process packets of data. When a packet processor receives a particular packet of data, the packet processor may produce what is commonly referred to as a search key. The search key may be hashed into an alternate form commonly referred to as a hashed search key. The search key may be used to determine what actions to perform on the packet as described in further detail below. Typically, a search key may be generated by the packet processor by extracting particular information in the packet header, e.g., source and destination address, source and destination port. Once the search key is generated, a tree search engine within the packet processor may access an entry in a table commonly referred to as a hash table using the search key. The hash table may comprise a plurality of entries that enables the tree search engine to access a particular entry in a data structure associated with the particular packet processor. The data structure may comprise data as to what actions, e.g., modifying packet, which port of packet processor to forward packet, the packet processor should perform on the packet.
As stated above, the search key may be used to access an entry in a data structure by a tree search engine. The particular entry in the data structure may be accessed by accessing a particular entry in the hash table. Since a search key may be hundreds of bits long, the tree search engine may use only certain bits to determine which entry to access in the hash table. Consequently, one or more entries may be accessed in the hash table by the same search key thereby causing a conflict. These conflicts may be resolved by what is commonly referred to as a Practical Algorithm To Retrieve Information Coded in Alphanumeric (Patricia) Tree. A Patricia Tree structure may typically be stored in a memory, e.g., Static Random Access Memory (SRAM), external to the tree search engine. A Patricia Tree may test appropriate bits in the search key to distinguish one entry in the direct table from another. Details regarding testing appropriate bits are discussed in “Patricia—Practical Algorithm to Retrieve Information Coded in Alphanumeric”, Journal of the ACM, Vol. 15, 1968.
A search key may also be used to access a particular entry in a data structure using a Content Addressable Memory (CAM) instead of using a Patricia Tree structure and hash table. It is noted that the search key need not be hashed when a CAM is used to access a particular entry in a data structure. A CAM may refer to a memory that is accessed by comparing the content of the data stored rather than by addressing predetermined locations. A CAM may comprise entries where each of those entries may store a particular pointer to a data structure entry associated with a particular search key. By storing a particular pointer equivalent to a data structure entry, conflicts, i.e., collisions, may be avoided. Subsequently, an advantage of implementing a CAM versus a Patricia Tree structure to search for a particular entry in the data structure is that the search may be conducted faster since there may be no collisions. However, a CAM is more expensive than implementing the low cost memory that stores the Patricia Tree structure used by the tree search engine.
It would therefore be desirable to develop a system that allows some searches to be accomplished by the tree search engine using a lower cost memory and other searches accomplished using the higher cost but faster CAM.